package cl.regex;

import java.util.Stack;

import cl.nfa.NFA;

public class Matcher {
    
    private NFA nfa;
    
    public boolean match(String pattern, String value) {
        nfa = createNFA(pattern);
        
        System.out.println(nfa);
        
        for(int i = 0;i < value.length(); i++) {
            nfa.gobble(value.charAt(i));
        }
        
        return nfa.isMatching();
    }
    
    private NFA createNFA(String pattern) {
        Stack<NFA> nfaStack = new Stack<NFA>();
        Stack<Character> operatorStack = new Stack<Character>();
        boolean concatNext = false;
        
        for(int i = 0;i < pattern.length(); i++) {
            char ch = pattern.charAt(i);
            
            if(isInput(ch)) {
                nfaStack.push(createBasicNFA(ch));
                
                if(concatNext) {
                    operatorStack.push(',');
                }
                
                concatNext = true;
            } else {
                operatorStack.push(ch);
                
                if(ch == '*') {
                    concatNext = true;
                } else {
                    concatNext = false;
                }
            }
        }
        
        while(!operatorStack.isEmpty()) {
            evaluate(nfaStack, operatorStack);
        }
        
        NFA nfa = nfaStack.pop();
        nfa.setTerminating(true, nfa.numStates() - 1);
        nfa.setStartState(0);
        
        return nfa;
    }
    
    private boolean isInput(char ch) {
        return ch != '|' && ch != '*' && ch != '+';
    }
    
    private void evaluate(Stack<NFA> nfaStack, Stack<Character> operatorStack) {
        char ch = operatorStack.pop();
        
        switch(ch) {
        case '*':
            star(nfaStack);
            break;
        case '|':
            union(nfaStack);
            break;
        case ',':
            concat(nfaStack);
            break;
        default:
            System.err.println("Unknown operator: " + ch);
            
        }
    }
    
    private NFA createBasicNFA(char value) {
        NFA nfa = new NFA();
        
        nfa.addState();
        nfa.addState();
        
        nfa.addConnection(value, 0, 1);
        
        return nfa;
    }
    
    private void star(Stack<NFA> stack) {
        NFA nfa = stack.pop();
        
        nfa.addConnection(NFA.EPSILON, 0, nfa.numStates() - 1);
        nfa.addConnection(NFA.EPSILON, nfa.numStates() - 1, 0);
        
        stack.push(nfa);
    }
    
    private void union(Stack<NFA> stack) {
        NFA nfa = stack.pop();
        NFA nfa2 = stack.pop();
        
        int length = nfa2.numStates();
        nfa2.merge(nfa);
        
        nfa2.addConnection(NFA.EPSILON, 0, length);
        nfa2.addConnection(NFA.EPSILON, length - 1, nfa2.numStates() - 1);
        
        stack.push(nfa2);
    }
    
    private void concat(Stack<NFA> stack) {
        NFA nfa = stack.pop();
        NFA nfa2 = stack.pop();
        
        int length = nfa2.numStates();
        nfa2.merge(nfa);
        
        nfa2.addConnection(NFA.EPSILON, length - 1, length);
        
        stack.push(nfa2);
    }
    
    public static void main(String[] args) {
        Matcher matcher = new Matcher();
        
        System.out.println(matcher.match("a*a", ""));
    }
}
